package com.lw.leetcode.arr.c;

/**
 * 765. 情侣牵手
 *
 * @Author liw
 * @Date 2021/9/19 14:10
 * @Version 1.0
 */
public class MinSwapsCouples {

    public static void main(String[] args) {
        MinSwapsCouples test = new MinSwapsCouples();

        // 1
        int[] arr = {0, 2, 1, 3};

        int i = test.minSwapsCouples(arr);
        System.out.println(i);
    }


    private int[] arr;
    private int[] row;

    public int minSwapsCouples(int[] row) {
        int length = row.length;
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            arr[row[i]] = i;
        }
        this.arr = arr;
        this.row = row;
        int sum = 0;
        for (int i = 0; i < length; i += 2) {
            if (row[i] == -1) {
                continue;
            }
            int count = find(row[i], row[i + 1]);
            row[i] = -1;
            row[i + 1] = -1;
            sum += count - 1;
        }
        return sum;

    }

    private int find(int a, int b) {
        int c = (a & 1) == 0 ? a + 1 : a - 1;
        int size = 0;
        if (c != b) {
            int i = arr[c];
            int j = (i & 1) == 0 ? i + 1 : i - 1;
            int v = row[j];
            row[j] = -1;
            row[i] = -1;
            size = find(v, b);
        }
        return size + 1;
    }

}
